Content addressable memory (CAM) devices enjoy a wide variety of applications, including conventional search engine systems. A search engine system can typically include one or more search engine devices. A search engine device can include circuitry for performing one or more types of search operations. In a search operation, a comparand (or key) may be compared to multiple entries to see if all or a portion of the key matches an entry. After a search operation, a search engine may give a search result as an output. Typically a search result may include an “index” value, which may be used to access associated data or may include associated data itself.
A CAM device, can be a preferred type of search engine system device. CAM devices can be capable of executing search operations faster than many other conventional approaches, such as those based in general purpose processors executing a search algorithm. CAM devices are typically based on particular types of CAM cells. Such CAM cells may include storage circuits integrated with compare circuits. Storage circuits may include, without limitation, storage circuits based on static random access memory (SRAM) type cells or dynamic random access memory (DRAM) type cells. Alternate approaches may include random access memories (RAM) arrays, or the like, with separate matching circuits and/or processes.
As with most integrated circuit devices, a desirable feature in a CAM device can be a rate at which compare operations can be executed. In many cases, an overall rate at which a conventional CAM device can generate results can be related to a number of entries that have to be searched.
In addition, power consumption is almost always an important factor for any integrated circuit. Lower power consumption in a device can allow for smaller power supplies and peak current requirements for a device and/or system.
A CAM may perform a search function described above by applying a search key or “comparand” to a table of stored data values. A CAM may then determine if any of the data values matches a given search key. A typical conventional search operation, along with a general architecture of a conventional CAM system will now be described in more detail.
Referring now to FIG. 10, a conventional CAM device is set forth in a block diagram and designated by the general reference character 1000. A conventional CAM device 1000 may include a number of entries (ENTRY0 to ENTRYn) 1002 and a priority encoder 1004. Each entry (ENTRY0 to ENTRYn) may store a data value for comparison with an applied key value KEY. In a conventional compare operation, a key value KEY can be applied to entries (ENTRY0 to ENTRYn) essentially simultaneously. That is, a key value KEY can be applied to all entries (ENTRY0 to ENTRYn).
Each entry (ENTRY0 to ENTRYn) can generate a corresponding match indication (MATCH0 to MATCHn) that can reflect whether or not data for an entry matches an applied key value. More particularly, if entry data matches a key value, a corresponding match indication can be active. If entry data does not match a key value, a corresponding match indication can be inactive.
Priority from among multiple active match indications can be established by a priority encoder 1004. More particularly, a conventional priority encoder 1004 can prioritizes match indication according to a “physical” priority of the entries. A physical priority can be a priority established by a physical location of an entry on a conventional CAM device. Typically, physical priority can correspond to an address of an entry, with lower address values having priority over higher address values.
In the example of FIG. 10, a priority encoder 1004 can encode a highest priority match indication into an index value INDEX. In some conventional approaches, an index value can be used to access associated data, or alternative, a highest priority match indication can access associated data directly.
In a conventional approach, some entries may be considered “invalid” and thus may be excluded from generating a match indication. Conventionally, invalid entries can be distinguished from valid entries by a valid bit. That is, valid entries may have a valid bit set to one value (e.g., 1), while invalid entries may have a valid bit set to another value (e.g., 0). In a conventional compare operation, a valid bit value of “1” may be applied in combination with a key, thus forcing invalid entries to “not match” a key value. However, a key value can still be applied to such invalid entries.
A drawback to conventional approaches can be limited flexibility in how data may be stored within CAM entries. As shown in FIG. 10, a typical conventional CAM can include entries accessible by a single addressable space that establishes a hard priority. If a large number of new data values needs to be entered, such data values have to be inserted at an appropriate address, and all lower priority values will have to be shifted to lower priority locations.
In light of the above, it would be desirable to arrive at a CAM device that can provide greater flexibility in the manner in which data may be stored in CAM entries.
In addition, or alternatively it would be desirable to arrive at CAM device that may provide search result values at a faster rate than conventional approaches.
Still further, it would be desirable to arrive at CAM device that may consume less power than conventional CAM devices.